import java.util.Scanner;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-22
 * Time:20:58
 */
public class TestDemo {
    /**
     * 440. 字典序的第K小数字
     * 给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字
     * 输入: n = 13, k = 2
     * 输出: 10
     * 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，
     * 所以第二小的数字是 10。
     *
     * 。*/
    public int findKthNumber(int n, int k) {
        int index = 1;//第一字典序小的(就是1)
        int prefix = 1;//前缀从1开始
        while (index < k) {
            int count = getCount(prefix, n);
            //2. 第k个数在当前前缀下 往子树里面去看
            if (index + count > k) {
                prefix *= 10;//往下层遍历
                index++;//一直遍历到第K个推出循环
            } else if (index + count <= k) { //3.第k个数不在当前前缀下,当前的前缀小了嘛，我们扩大前缀
                prefix++;//去下个前缀遍历
                index += count;////跨过了一个前缀
            }
        }//退出循环时 cur==k 正好找到
        return prefix;
    }
    //1.确定指定前缀下所有子节点数:用下一个前缀的起点减去当前前缀的起点;
    //当 next 的值大于上界的时候，那以这个前缀为根节点的十叉树就不是满十叉树了啊，
    // 应该到上界那里，后面都不再有子节点因此  count += Math.min(n + 1, next) - cur
    private int getCount(int prefix, int n) {
        int count = 0;
        long cur = prefix;//不断向下层遍历可能一个乘10就溢出了, 所以用long
        long next = prefix + 1;
        while (cur <= n) {
            //用下一个前缀的起点减去当前前缀的起点
            count += Math.min(n + 1, next) - cur;
            cur *= 10;
            next *= 10;//往下层走
        }
        return count;
    }

    //另类加法
    public int Add(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        while (num2 != 0) {
            int sum = num1 ^ num2;
            int tmp = (num1 & num2) << 1;
            num1 = sum;
            num2 = tmp;
        }
        return num1;
    }

    //判断三条边是否能组成一个三角形
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            double a = scanner.nextDouble();
            double b = scanner.nextDouble();
            double c = scanner.nextDouble();
            if (ifTriangle(a, b, c)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    private static boolean ifTriangle(double a, double b, double c) {
        if (a + b > c && a + c > b && c + b > a) {
            return true;
        }
        return false;
    }
}
